package com.huangyi;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //计算右侧小于当前元素的个数
        class Solution {
            int[] index;   // 记录每个元素的“原始下标”，在归并过程中只搬动下标
            int[] tmp;     // 临时数组，用来辅助归并排序（保存下标，不保存值）
            int[] counts;  // 结果数组，counts[i] = nums[i] 右侧比它小的数量

            public List<Integer> countSmaller(int[] nums) {
                int n = nums.length;
                tmp = new int[n];
                counts = new int[n];
                index = new int[n];

                // 初始化下标数组，初始时 index[i] = i
                for (int i = 0; i < n; i++) {
                    index[i] = i;
                }

                // 分治归并排序
                mergeSort(nums, 0, n - 1);

                // 把 counts 数组转成 List<Integer> 返回
                List<Integer> list = new ArrayList<>(n);
                for (int v : counts) list.add(v);
                return list;
            }

            public void mergeSort(int[] nums, int left, int right) {
                if (left >= right) return;  // 递归基：区间只有一个元素时结束

                int mid = left + (right - left) / 2;
                // 递归排序左半区
                mergeSort(nums, left, mid);
                // 递归排序右半区
                mergeSort(nums, mid + 1, right);

                int cur1 = left, cur2 = mid + 1, k = 0;

                // 合并两个有序区间（这里用“降序”方式）
                while (cur1 <= mid && cur2 <= right) {
                    if (nums[index[cur1]] <= nums[index[cur2]]) {
                        // 如果右边的值更大或相等，先把右边的下标放进 tmp
                        tmp[k++] = index[cur2++];
                    } else {
                        // 如果左边的值更大：
                        // 说明右边 [cur2..right] 的元素全都比它小
                        counts[index[cur1]] += (right - cur2 + 1);
                        // 把这个左边元素的下标放进 tmp
                        tmp[k++] = index[cur1++];
                    }
                }

                // 把左半区剩余元素拷贝进 tmp
                while (cur1 <= mid) tmp[k++] = index[cur1++];
                // 把右半区剩余元素拷贝进 tmp
                while (cur2 <= right) tmp[k++] = index[cur2++];

                // 回写：把 tmp 里的结果拷回到 index 数组对应区间
                for (int j = left; j <= right; j++) {
                    index[j] = tmp[j - left];
                }
            }
        }


        //翻转对
        class Solution2 {
            int[] tmp;
            int result;

            public int reversePairs(int[] nums) {
                tmp = new int[nums.length];
                mergeSort(nums, 0, nums.length - 1);
                return result;
            }

            // 只做副作用统计与排序，不用返回值累计
            public void mergeSort(int[] nums, int left, int right){
                if (left >= right) return;

                int mid = left + (right - left) / 2;

                mergeSort(nums, left, mid);
                mergeSort(nums, mid + 1, right);

                // 先统计：左右两段各自已升序
                int j = mid + 1;
                for (int i = left; i <= mid; i++) {
                    while (j <= right && (long)nums[i] > 2L * (long)nums[j]) j++;
                    // 右半段 [mid+1, j-1] 都满足 nums[i] > 2*nums[?]
                    result += (j - (mid + 1));
                }

                // 再归并：标准升序合并
                int cur1 = left, cur2 = mid + 1, k = 0;
                while (cur1 <= mid && cur2 <= right) {
                    if (nums[cur1] <= nums[cur2]) {
                        tmp[k++] = nums[cur1++];
                    } else {
                        tmp[k++] = nums[cur2++];
                    }
                }
                while (cur1 <= mid)  tmp[k++] = nums[cur1++];
                while (cur2 <= right) tmp[k++] = nums[cur2++];

                // 回写
                for (int t = 0; t < k; t++) {
                    nums[left + t] = tmp[t];
                }
            }
        }

    }
}